A B-tree is a specialized multiway tree data structure that is designed for organizing data records for efficient data retrieval, especially when the data records are stored on a relatively slow storage media, such as a hard drive. Each node in a B-tree stores multiple keys for identifying the corresponding data records and pointers to child nodes of that node. The number of keys a node may store depends on the “order” of the B-tree. In a B-tree of order K, each node should contain from K to 2K keys. Using a larger K allows the B-tree to have a smaller height (or depth) for a given set of data records, thereby reducing the number of disk access that may be required to locate a desired data record.
The B-tree data structure may be used for organizing various types of data. For instance, a B-tree may be used for a hierarchical namespace in which the names are stored as keys in the B-tree. As an example, it has been proposed to use a B-tree for storing the metadata of a file system. In that application, the keys of the B-tree are the full pathnames of each file or directory. Most file system operations can be performed efficiently on such a data structure. Nevertheless, one important exception has been the rename operation. When a directory of the file system is to be renamed, the keys for all the nodes in the B-tree corresponding to files and subdirectories in that directory have to be changed accordingly. A naïve implementation of the rename operation would touch every file or subdirectories in the directory being renamed, which could be very inefficient. Conventionally, due to the inefficiency of the rename operation using the conventional approach, there has been the view that the B-tree data structure is unsuitable for managing a file system.